142.环形链表 II

• leetcode 链接
• 本文的思考基于代码随想录的题解，代码随想录的链接
  • 看过题解后，有下面问题的疑惑，再来阅读本文，阅读体验更好
• 本文内容为介绍我学习时遇到的两个问题，并讲述我自己解决问题的思考过程

为什么第一次在环中相遇，slow 的 步数 是 x+y 而不是 x + 若干环的长度 + y 呢

我的疑惑

• 我一直用两个人在环里跑步的比喻来思考这个问题。
• 那时我就在思考，如果跑的快的人（设为 A），只比跑的慢的人（设为 B）只快一丢丢呢。那如何保证 第一次在环中相遇，slow 的 步数 是 x+y 。

解决

• 后面我才发现，我们一直设定 A 的速度是二倍速，根本不存在我的问题
• 然后我依据二倍速这个条件，想象出一个场景，这有助于理解问题
• B 跑一圈的时间，A 必能跑两圈，B 跑半圈的时间，A 必能跑一圈。
• 继续想象一下，B 终于跑进环入口了，B 想跑完一圈，但 B 跑一圈的时间，A 能跑两圈，而此时 A 在环内。在这种情况下，A 必然能在 B 跑完一圈之前，直接超过 B 啊，难道你看不起 A 二倍速的实力？

为什么这两个指针每次只走一个节点， 相遇的时候就是 环形入口的节点。

具体描述

整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里 n 一定是大于等于 1 的，因为 fast 指针至少要多走一圈才能相遇 slow 指针。

这个公式说明什么呢？

先拿 n 为 1 的情况来举例，意味着 fast 指针在环形里转了一圈之后，就遇到了 slow 指针了。

当 n 为 1 的时候，公式就化解为 x = z，

这就意味着，从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。

我的疑惑

• 为什么这两个指针每次只走一个节点，就能相遇。当时我满脑袋在想，这个公式不是基于 fast 指针是二倍速相遇的时候求出来的吗？为什么现在都是一倍速，就能完成相遇
• 即下图划线处
  • 

解决

• 后发现，这根本不是一个二倍速的问题，而是一个数学公式的问题
• 这个解法里只有第一次相遇用到了二倍配速
• 我们通过第一次相遇，求出了 x（头结点） 和 z（第一次相遇点） 之间的关系。这个就代表着这 x 和 z 的关系
• 具体公式上 x = (n - 1) (y + z) + z
  • 其意思是，只要一个指针从头结点出发，另一个指针从第一次相遇点出发，那么结果就是第一个指针走完 x 的距离，第二个指针走完 z + （n-1）圈的距离。
  • 这两个距离的终点都是环入口，这是由公式决定的
  • 公式决定了这个两个距离是相等的，所以后续可以用一倍速相遇

题目总结

• 最后总结一下我们应该如何在这道题中形成自己解题的思维，关键点在于理解起点和终点

• 我们一开始用二倍速求出一个四个变量 x y z n 之间的特殊关系。这还只是一个整理前的式子

  • (x + y) * 2 = x + y + n (y + z)

• 针对我们想解决的问题：“找到环入口”，我们可以从关系中找到三个和环入口有关系的变量 xyz。

  • x（头结点（起点）到环入口（终点）的距离），
  • z（从第一次相遇点到环入口（终点）的距离），
  • y（从环入口（终点）到相遇点的距离）。

• 此时我们还有两个位置信息，头结点（起点）和第一次相遇点

• 现在我们尝试找出 x 和 z 的一些正比关系，这样我们就可以结合上一条的位置信息，把指针设定到 x 的起点，z 的起点。然后让两个指针按照正比关系去移动，那就能同时到达终点（环入口）

• 题外话：

  • 至于为什么想到用二倍速求出并整理式子搞出这个关系，我还没有想明白。先记住吧
  • 用时：整理思路 + 排版 + 复查 + 上传 = 45 分钟

答案

public class Solution
{
    public ListNode detectCycle(ListNode head)
    {
        //是否有环
        ListNode slow = head;
        ListNode fast = head;

        //用二倍速来测出有无 fast快人 能不能往回跑超过 slow慢人
        //这循环条件怎么写，主要是没用环怎么让他停止，对啊，指向 null 啊，链表特性都差点忘了
        while (fast != null && fast.next != null)
        {
            slow = slow.next;
            fast = fast.next.next; //要保证 fast.next 不是空指针，算是链表使用的代码细节了
            if (slow == fast)
                break;
        }
        //一条不会返回的跑道，快人跑到尽头了
        if (fast == null||fast.next == null)//示例三的情况要考虑道
            return null;

        //第二场跑步
        ListNode index1 = head; //从头结点出发
        ListNode index2 = fast; //从相遇点出发

        while (index1 != index2)
        {
            index1 = index1.next;
            index2 = index2.next;
        }
        return index1;
    }
}